<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>DoublyLinkedList</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(data) {
          this.data = data;
          this.previous = null;
          this.next = null;
        }
      }
      class DoublyLinkedList {
        constructor() {
          this.head = null;
          this.tail = null;
          this.length = 0;
        }
        append(element) {
          let newNode = new Node(element);
          if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
          } else {
            newNode.previous = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
          }
          this.length += 1;
        }
        insert(position, element) {
          if (position < 0 || position > this.length) {
            return false;
          }
          let newNode = new Node(element);
          if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
          } else {
            if (position === 0) {
              this.head.previous = newNode;
              newNode.next = this.head;
              this.head = newNode;
            } else if (position === this.length) {
              newNode.previous = this.tail;
              this.tail.next = newNode;
              this.tail = newNode;
            } else {
              let index = 0,
                current = this.head;
              while (index++ < position) {
                current = current.next;
              }
              newNode.next = current;
              newNode.previous = current.previous;
              current.previous.next = newNode;
              current.previous = newNode;
            }
          }
          this.length += 1;
        }
        get(position) {
          if (position < 0 || position >= this.length) {
            return null;
          }
          let current = null,
            index = 0;
          if (position < this.length / 2) {
            current = this.head;
            index = 0;
            while (index++ < position) {
              current = current.next;
            }
          } else {
            current = this.tail;
            index = this.length - 1;
            while (index-- > position) {
              current = current.previous;
            }
          }
          return current.data;
        }
        indexOf(element) {
          let current = this.head,
            index = 0;
          while (current) {
            if (current.data === element) {
              return index;
            }
            current = current.next;
            index += 1;
          }
          return -1;
        }
        update(position, element) {
          if (position < 0 || position >= this.length) {
            return false;
          }
          let current = null,
            index = 0;
          if (position < this.length / 2) {
            current = this.head;
            index = 0;
            while (index++ < position) {
              current = current.next;
            }
            current.data = element;
          } else {
            current = this.tail;
            index = this.length - 1;
            while (index-- > position) {
              current = current.previous;
            }
            current.data = element;
          }
          return true;
        }
        removeAt(position) {
          if (position < 0 || position >= this.length) {
            return null;
          }
          let current = null,
            preCurrent = null,
            nextCurrent = null,
            index = 0;
          if (this.length === 1) {
            this.head = null;
            this.tail = null;
          } else {
            if (position === 0) {
              current = this.head;
              this.head = this.head.next;
              this.head.next.previous = null;
            } else if (position === this.length - 1) {
              current = this.tail;
              this.tail.previous.next = null;
              this.tail.previous = null;
            } else if (position < this.length / 2) {
              current = this.head;
              while (index++ < position) {
                preCurrent = current;
                current = current.next;
              }
              preCurrent.next = current.next;
              current.next.previous = preCurrent;
            } else {
              current = this.tail;
              index = this.length - 1;
              while (index-- > position) {
                nextCurrent = current;
                current = current.previous;
              }
              nextCurrent.previous = current.previous;
              current.previous.next = nextCurrent;
            }
          }
          this.length -= 1;
          return current.data;
        }
        remove(element) {
          return this.removeAt(this.indexOf(element));
        }
        isEmpty() {
          return this.length === 0;
        }
        size() {
          return this.length;
        }
        getHead() {
          return this.head.data;
        }
        getTail() {
          return this.tail.data;
        }
        // 转字符串
        toString() {
          return this.backwardString();
        }
        forwardString() {
          let current = this.tail,
            str = "";
          while (current) {
            str += current.data + " ";
            current = current.previous;
          }
          return str;
        }
        backwardString() {
          let current = this.head,
            str = "";
          while (current) {
            str += current.data + " ";
            current = current.next;
          }
          return str;
        }
      }
      let doublyLinkedList = new DoublyLinkedList();
      doublyLinkedList.append("a");
      doublyLinkedList.append("b");
      doublyLinkedList.append("c");
      doublyLinkedList.append("d");
      doublyLinkedList.append("e");
      doublyLinkedList.append("f");
      // console.log(doublyLinkedList.backwardString());
      // console.log(doublyLinkedList.forwardString());
      doublyLinkedList.insert(2, "zzz");
      // console.log(doublyLinkedList.toString());
      // console.log(doublyLinkedList.get(5));
      // console.log(doublyLinkedList.get(6));
      // console.log(doublyLinkedList.indexOf("f"));
      // console.log(doublyLinkedList.update(6, "xxx"));
      // console.log(doublyLinkedList.toString());
      // console.log(doublyLinkedList.removeAt(2));
      console.log(doublyLinkedList.remove("a"));
      console.log(doublyLinkedList.toString());
      console.log(doublyLinkedList.getHead());
      console.log(doublyLinkedList.getTail());
    </script>
  </body>
</html>
